# -*- coding: utf-8 -*- 
# @project : 《剑指offer》
# @Author : created by bensonrachel on 2021/6/10
# @File : 机器人的运动范围DFS.py

class Solution(object):
    def movingCount(self, k, rows, cols):
        """
        :type threshold: int
        :type rows: int
        :type cols: int
        :rtype: int
        """

        def is_val(a, b):#判断是否小于等于K的函数
            x = a
            y = b
            if (a >= 10): x = int(str(a)[0]) + int(str(a)[1])#数位之和
            if (b >= 10): y = int(str(b)[0]) + int(str(b)[1])
            return (x + y <= k)

        def dfs(a, b, tag):#深度优先，递归
            w = 0
            q = tag
            if (0 <= b - 1 < cols and is_val(a, b - 1)):#先判断四个下一步能否进去，能就进去递归
                if (matric[a][b - 1] == 0):
                    matric[a][b - 1] = 1
                    z = dfs(a, b - 1, q)
                    tag = z + tag#将这一层进去里面的返回来加上
                    w += 1#***进去一个说明这一层多一个
            if (0 <= b + 1 < cols and is_val(a, b + 1)):
                if (matric[a][b + 1] == 0):
                    matric[a][b + 1] = 1
                    z = dfs(a, b + 1, q)
                    tag = z + tag
                    w += 1
            if (0 <= a - 1 < rows and is_val(a - 1, b)):
                if (matric[a - 1][b] == 0):
                    matric[a - 1][b] = 1
                    z = dfs(a - 1, b, q)
                    tag = z + tag
                    w += 1
            if (0 <= a + 1 < rows and is_val(a + 1, b)):
                if (matric[a + 1][b] == 0):
                    matric[a + 1][b] = 1
                    z = dfs(a + 1, b, q)
                    tag = z + tag
                    w += 1
            if (w != 0):
                tag += w
                # print("/")
                return tag
            else:
                return 0#如果一个都没进下一层，就代表所有下一层加起来为0

        matric = []
        for i in range(rows):
            matric.append([0] * cols)#新建一个记录数组，全为0的二维数组
        if (cols == 0 or rows == 0): return 0
        matric[0][0] = 1
        tag = dfs(0, 0, 0)
        return tag + 1#这里跟上面三个星号的地方属于同意思。

